package lc;

import org.junit.Test;

public class Ex727 {

    //从s1找到一个子串，使得他的一个子序列是s2, 如abcd, bd, 那么从s1中取出bcd即可
    //返回最左且最短的那个
    public String minSubArray(String s1, String s2) {
        char[] cs = s1.toCharArray(), ss = s2.toCharArray();
        int m = cs.length, n = ss.length;
        int i = 0, j = 0, limit = m - n;
        String res = null;
        while (i <= limit) {
            while (i < limit && cs[i] != ss[j]) { 
                i++;
            }
            if (i > limit) break;
            int start = i;
            while (i < limit && j < n) {
                if (cs[i] == ss[j]) {
                    j++;
                }
                i++;
            }
            if (j < n) break;
            if (res == null || i - start < res.length()) {
                res = new String(cs, start, i - start);
            }
            i = start + 1;
            j = 0;
        }
        return res == null ? "" : res;
    }

    @Test
    public void test() {
        System.out.println(minSubArray("abcdebdde", "bde"));
    }
}
